package com.data.construct.linkedList;

import java.util.NoSuchElementException;

/**
 * 双链表代码实现
 * 关键点一、同时持有头尾节点的引用
 * 关键点二、虚拟头尾节点
 * 关键点三、内存泄露, 节点的上下节点引用问题?
 *
 * @author sunhl
 * @Description:
 * @Date: created in 2024/10/22 0022 9:57
 * @Modified By:
 */
public class MyDoubleLinkedList<E> {
    // 虚拟头尾节点
    final private DoubleNode<E> head;
    final private DoubleNode<E> tail;

    private int size;

    /**
     * 构造函数初始化虚拟头尾节点
     */
    public MyDoubleLinkedList() {
        this.head = new DoubleNode<>(null);
        this.tail = new DoubleNode<>(null);
        head.next = tail;
        tail.prev = head;
        this.size = 0;
    }

    /**
     * 尾部增
     */
    public void addLast(E e) {
        DoubleNode<E> x = new DoubleNode<>(e);
        DoubleNode<E> temp = tail.prev;
        // temp <-> tail

        temp.next = x;
        tail.prev = x;

        x.next = tail;
        x.prev = temp;
        // temp <-> x <-> tail

        size++;
    }

    /**
     * 首部增
     */
    public void addFirst(E e) {
        DoubleNode<E> x = new DoubleNode<>(e);
        DoubleNode<E> temp = head.next;
        // head <-> temp

        temp.prev = x;
        head.next = x;

        x.next = temp;
        x.prev = head;
        // head <-> x <-> temp

        size++;
    }

    /**
     * 指定索引增
     */
    public void add(int index, E element) {
        checkPositionIndex(index);
        if (index == size) {
            addLast(element);
            return;
        }

        // 找到 index 对应的 Node
        DoubleNode<E> p = getNode(index);
        DoubleNode<E> temp = p.prev;
        // temp <-> p

        // 新要插入的 Node
        DoubleNode<E> x = new DoubleNode<>(element);

        p.prev = x;
        temp.next = x;

        x.prev = temp;
        x.next = p;

        // temp <-> x <-> p

        size++;
    }

    /**
     * 删首位
     *
     * @return
     */
    public E removeFirst() {
        if (size < 1) {
            throw new NoSuchElementException();
        }

        // 虚拟节点的存在是我们不用考虑空指针的问题
        DoubleNode<E> x = head.next;
        DoubleNode<E> temp = head.next.next;
        // head <-> x <-> temp

        head.next = temp;
        temp.prev = head;

        x.prev = null;
        x.next = null;
        // head <-> temp

        size--;
        return x.val;
    }

    /**
     * 删末尾
     *
     * @return
     */
    public E removeLast() {
        if (size < 1) {
            throw new NoSuchElementException();
        }

        // 虚拟节点的存在是我们不用考虑空指针的问题
        DoubleNode<E> x = tail.prev;
        DoubleNode<E> temp = tail.prev.prev;
        // temp <-> x <-> tail

        tail.prev = temp;
        temp.next = tail;

        x.prev = null;
        x.next = null;
        // temp <-> tail

        size--;
        return x.val;
    }

    /**
     * 指定索引删
     *
     * @param index
     * @return
     */
    public E remove(int index) {
        checkElementIndex(index);

        // 找到 index 对应的 Node
        DoubleNode<E> x = getNode(index);

        DoubleNode<E> prev = x.prev;
        DoubleNode<E> next = x.next;
        // prev <-> x <-> next

        prev.next = next;
        next.prev = prev;

        x.prev = null;
        x.next = null;
        // prev <-> next

        size--;
        return x.val;
    }

    /**
     * 指定索引查
     *
     * @param index
     * @return
     */
    public E get(int index) {
        checkElementIndex(index);
        // 找到 index 对应的 Node
        DoubleNode<E> p = getNode(index);

        return p.val;
    }

    /**
     * 查首位
     *
     * @return
     */
    public E getFirst() {
        if (size < 1) {
            throw new NoSuchElementException();
        }

        return head.next.val;
    }

    /**
     * 查末尾
     *
     * @return
     */
    public E getLast() {
        if (size < 1) {
            throw new NoSuchElementException();
        }

        return tail.prev.val;
    }

    /**
     * 改指定索引
     *
     * @param index
     * @param val
     * @return
     */
    public E set(int index, E val) {
        checkElementIndex(index);
        // 找到 index 对应的 Node
        DoubleNode<E> p = getNode(index);

        E oldVal = p.val;
        p.val = val;

        return oldVal;
    }


    // ***** 其他工具函数 *****

    /**
     * 链表大小
     *
     * @return
     */
    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 根据索引获取节点
     *
     * @param index
     * @return
     */
    private DoubleNode<E> getNode(int index) {
        checkElementIndex(index);

        // 通过 index 判断从 head 还是 tail 开始遍历
        DoubleNode<E> p;
        if (size / 2 > index) {
            p = head.next;
            for (int i = 0; i < index; i++) {
                p = p.next;
            }
        } else {
            p = tail.prev;
            for (int i = size - 1; i > index; i--) {
                p = p.prev;
            }
        }

        return p;
    }

    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }

    // 检查 index 索引位置是否可以存在元素
    private void checkElementIndex(int index) {
        if (!isElementIndex(index)) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }

    // 检查 index 索引位置是否可以添加元素
    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index)) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }

    private void display() {
        System.out.println("size = " + size);
        for (DoubleNode<E> p = head.next; p != tail; p = p.next) {
            System.out.print(p.val + " <-> ");
        }
        System.out.println("null");
        System.out.println();
    }

    public static void main(String[] args) {
        MyDoubleLinkedList<Integer> list = new MyDoubleLinkedList<>();
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        list.addFirst(0);
        list.add(2, 100);
        Integer integer = list.get(1);
        Integer integer2 = list.get(4);

        list.display();
        // size = 5
        // 0 <-> 1 <-> 100 <-> 2 -> 3 -> null
    }
}
